/**
 * Created by sunchenglin on 2017/7/17.
 * 快排
 //    冒泡排序
 //    选择排序
 //    插入排序
 //    希尔排序
 //    归并排序
 //    快排
 //    计数排序
 //    桶排序
 //    基数排序
 //    拓扑排序
 //    外部排序
 */
public class Solution {
    public static void change(int i, int j, int[] array){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static int partition(int[] array, int left, int right){
        int base = left;
        left++;
        while(left<=right){
            while(array[left]<array[base] && left<=right)
                left++;
            while(array[right]>=array[base] && left<=right)
                right--;
            if(left<right){
                change(left,right,array);
            }
            if(left>right){
                left--;
            }
            if(left == right)
                break;
        }
        change(base,left,array);
        return left;
    }

    public static void quickSort(int[] array, int left, int right){
        if(left>=right) return;
        int p = partition(array,left,right);
        quickSort(array,left,p);
        quickSort(array,p+1,right);
    }
    public static void main(String args[]){
        int[] a={7,4,8,5,3,4,5,2,6};
        quickSort(a,0,a.length-1);
        System.out.println("haha");
    }
}
